package com.example.demo.zaqizabatest.sortalgorithm;

/**
 * @ClassName QuickSort1
 * @Author lys4134
 * @Date 2021/12/30 11:09:51
 * @Description QuickSort1
 * @Version 1.0
 **/
public class QuickSort1 {

    public int[] sortArray(int[] nums) {
        sort(nums);
        return nums;
    }

    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int lo, int hi) {

        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);	// 切分
        sort(a, lo, j - 1);	// 将左半部分排序
        sort(a, j + 1, hi);	// 将右半部分排序
    }

    private static int partition(int[] a, int lo, int hi) {
        // 将数组切分为a[lo,...,j-1],a[j],a[j+1,...hi]
        // 左右扫描指针, 此处 hi+1是因为，下面算法中从右访问用的是a[--j],
        // 虽然，从左访问同样是a[++i]，但因为我们的标志元素v用的是a[lo]，所以没有必要从最左边起自己和自己比一遍。
        int i = lo, j = hi + 1;	// 左右扫描指针
        int v = a[lo];	// 切分元素，标志元素

        while (true) {
            // 扫描左右，检查扫描是否结束并交换元素

            // 如果 a[lo+1,....,hi] 全比 v小 ，即 全比 a[lo]小， 就会触发 里面的break条件
            // 这个循环的作用是 让 i（左指针），移动到 >= v（即 >= a[lo]） 的地方
            while (less(a[++i], v)) {
                // 这里的跳出条件是跟边界匹配的，应对极端的直接移动到边界的情况
                // 为了不写更复杂的逻辑，所以直接写成匹配边界
                // 后面的稍微注意一下，就很省事
                if (i == hi) {
                    break;
                }
            }

            // 同理，这个循环的作用是让右指针j，移动到 a[j] <= v 的地方
            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            // 判断结束条件，如果 左指针 移到了 右指针 重合甚至更右的地方，就结束本轮
            if (i >= j) {
                break;
            }

//			exch(a, i, j);	 交换的作用
            // 现在是 a[i] > v > a[j]
            // 所以交换 a[i] 和 a[j]

            a[j] ^= a[i];
            a[i] ^= a[j];
            a[j] ^= a[i];
        }


//		exch(a, lo, j);	// 将 v = a[j] 放入正确的位置
        // 如果 i >= j ， 因为上面大循环内，第一个小循环就确保了： i及i左边的元素全部小于 a[lo],。
        // 所以目前a[j] < a[lo]， 那么交换 a[lo] 和 a[j] 就可以完成最终排序
        // 即 标志位 左边全小于&&右边全大于 标志
        // 交换a[lo] 和 a[j]

		/* 这里不能用异或，因为，i可能和j重合，自己和自己异或完变零了
		 *
		a[j] ^= a[lo];
		a[lo] ^= a[j];
		a[j] ^= a[lo];
		*/

        // 如果 i >= j ， 因为上面大循环内，第一个小循环就确保了： i左边的元素全部小于 a[lo]。
        // 第一个小循环出来有以下可能性：1、左游标当前所指大于等于标志位。
        // 2、左游标指向数组末尾，且该数据小于标志位
        // 3、左游标当前所指为数组末尾，且大于等于标志位。

        // 如果左右未相遇，
        // 那么右游标当前所指为任一小于等于标志位的元素。
        // 然后 左游标和右游标所指元素交换，交换后 左游标及左游标左边小于等于标志位
        // 大循环继续

        // 如果左右能相遇，那么退出大循环：
        // 第二个小循环根据第一个小循环有如下情况
        // 如果是 情况1 ，那么右游标 指向 左游标的左一位 或  和 左游标重合
        // 如果是 情况2， 那么右游标 指向 数组末尾，和左游标重合
        // 如果是 情况3， 那么右游标可能指向 数组末尾和左游标重合，也可能指向左游标右一位
        // 如果相遇了，则 左右游标目前并不做交换

        //
        // 左游标：左边小于等于标志位
        // 右游标：右边大于等于标志位
        // 若左右游标重合，则标志位任意和左右游标交换都没有问题
        // 若左游标在右游标右边 即
        // 右游标及右游标左边小于等于标志位  左游标及左游标右边大于等于标志位
        // 又因为我们的标志位是从最左边取的，说明被交换的元素，需要满足小于等于标志位
        // 故我们需要交换标志位和右游标。



        // 要和代表小的那一个交换，因为，标志位是取的数组最左侧
        // 核心在于：哪个游标指的数字应该是 小于等于 标志位的
        // 我们就应该把标志位和哪个游标交换
        // 交换完要满足左边的全比 lo 标志的小， 所以 右游标 和 lo交换，
        // 交换后  nums[j] 左边全是比 nums[j] 小的

        int temp = a[lo];
        a[lo] = a[j];
        a[j] = temp;


        // 所以根据上面的分析，此处返回的下标应该是和标志位交换的那个下标
        // 即 返回 右游标
        return j;	// a[lo,...,j-1] <= a[j] <= a[j+1,....,hi]达成
    }

    // 判断a是否小于v
    public static boolean less(int a, int v) {
        return a < v;
    }

}
